package demo;

/**
 *    最长上升子序列
 */
class Solution30 {
	public int lengthOfLIS(int[] nums) {
		int[] dp = new int[nums.length];
		dp[0] = 1;
		int max = dp[0];
		for (int i = 1; i < nums.length; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			max = max > dp[i] ? max : dp[i];
		}
		return max;
	}
}

